from typing import List


class SegmentTree:
    def __init__(self, elements):
        self.size = len(elements)
        n = self.tableSize(self.size) + 1
        self.n = n
        self.tree = [0] * (n * 2)
        for i, e in enumerate(elements):
            self.tree[i + n] = e
        i = n - 1
        while i > 0:
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])
            i -= 1
        print(self.tree)
        print(self.size)
        print(self.n)

    def merge(self, e1, e2):
        return e1 + e2

    def tableSize(self, n):
        a = n
        a |= a >> 1
        a |= a >> 2
        a |= a >> 4
        a |= a >> 8
        a |= a >> 16
        return a

    def update(self, i, e):
        self.tree[i + self.n] = e
        p = (i + self.n) // 2
        while p > 0:
            self.tree[p] = self.merge(self.tree[p*2], self.tree[p*2+1])
            p = p // 2

    # 注意，按照不成文的约定，包含 i 但不包含 j
    def query(self, i, j):
        n = self.n
        i += n
        j += n
        result = 0

        while i < j:
            if i % 2 == 1:
                result += self.tree[i]
                i += 1
            if j % 2 == 1:
                j -= 1
                result += self.tree[j]
            i //= 2
            j //= 2
        return result

class Solution:
    def __init__(self):
        self.stId = -1
        self.orderedMembers = []
        self.memberIdToNode = dict()
        self.graph = dict()
        self.st = SegmentTree([0])

    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:
        self.orderedMembers = [None] * (n + 1)
        self.leaderShipToGraph(leadership)
        print(self.graph)
        self.codeGraph(1, 0)
        print("Orderred Member Nodes:", self.orderedMembers)
        print("MemberId to Node:", self.memberIdToNode)
        self.st = SegmentTree([0]*n)

        result = []
        for op in operations:
            if op[0] == 1:
                self.coin1(op[1], op[2])
            elif op[0] == 2:
                self.coinGroup(op[1], op[2])
            elif op[0] == 3:
                result.append(self.query(op[1]) % 1000000007)
        return result

    def leaderShipToGraph(self, leadership: List[List[int]]):
        graph = dict()
        for [leader, member] in leadership:
            if leader not in graph:
                graph[leader] = []
            graph[leader].append(member)
        self.graph = graph

    def codeGraph(self, i, p):
        self.stId += 1
        currId = self.stId
        self.orderedMembers[currId] = {"member": i, "curr": currId}
        self.memberIdToNode[i] = self.orderedMembers[currId]
        if i in self.graph:
            for j in self.graph[i]:
                self.codeGraph(j, i)
        self.orderedMembers[currId]["end"] = self.stId + 1

    def coin1(self, memberId, coin):
        node = self.memberIdToNode[memberId]
        i = node["curr"]
        currCoins = self.st.query(i, i + 1)
        self.st.update(i, currCoins + coin)

    def coinGroup(self, memberId, coin):
        node = self.memberIdToNode[memberId]
        i, end = node["curr"], node['end']
        while i < end:
            currCoins = self.st.query(i, i + 1)
            self.st.update(i, currCoins + coin)
            i += 1

    def query(self, memberId):
        print(self.st.tree)
        node = self.memberIdToNode[memberId]
        i, end = node["curr"], node['end']
        return self.st.query(i, end)


solu = Solution()
n = 6
ls = [[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]]
ops = [[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]
print(solu.bonus(n, ls,  ops))
